题解 CF1167B@洛谷 | 1167B@Codeforces 【Lost Numbers】

我们有一个由 $4,8,15,16,23,42$ 组成的排列，只能询问四次两个位置上的数的乘积。

下面是一些可能会考虑到的错误的策略（也是我做题时的思路），在这里放出体现我们的思考过程：

策略 1：每次询问两个相同的下标 $i$ 和它本身。

这种策略是最容易想到的，但是这样的话只能询问出 $4$ 个位置的值，剩下两个位置就没办法了。考虑其它策略。

策略 2：询问 $1$ 与 $1$ 的乘积，得到第一个数，此后三次询问 $(1,2)(2,3)(3,4)$。

和策略 1 有着同样的问题。

正确策略

通过上面的思考，我们得到了一个结论：只有 $4$ 个位置是显然不行的，考虑添加第五个位置。

我们可以询问 $(1,2)(2,3)(3,4)(4,5)$，这样就能方便的获得和五个位置相关的信息。

具体解法

在按照上面的策略询问完前五个数后得到了四个答案（代码中记做 $mutiple$），我们枚举所有 $6!=720$ 种可能的排列情况，对于每个排列，循环一遍判断是否符合询问得到的答案即可。

但是这样还不够，我们还要知道满足四个答案的排列是唯一的。

唯一性证明

自己口胡的，可能不太严谨，但是自认为比较好理解，可以手玩几个理解一下。

因为上面数列任意两个数的乘积都不同，我们想到，满足 $a_i\times a_j=k$ 的只有两种可能，即 $i$ 与 $j$ 交换。而上面就相当于固定了前五个数，因为数列中的六个数给定，可以通过排除来获得第六个数的信息。

唯一性得证，策略正确。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int a[7] = {-1, 4, 8, 15, 16, 23, 42}, multiple[5];

int main() {
	for(int i=1;i<=4;i++) {
		printf("? %d %d\n", i, i+1);
		fflush(stdout);
		scanf("%d", &multiple[i]);
	}
	do {
		bool _ = true;
		for(int i=1;i<=4;i++) {
			if(a[i] * a[i+1] != multiple[i]) {
				_ = false;
				break;
			}
		}
		if(_) {
			printf("! ");
			for(int i=1;i<=6;i++) printf("%d ", a[i]);
			puts("");
			break;
		}
	}while(next_permutation(a+1, a+7));
	return 0;
}